﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
using namespace std;

 template< class K,class V>
 class AVLTreeNode
 {
 public:
	 pair<K, V> _kv;
	 AVLTreeNode<K, V>* _left;
	 AVLTreeNode<K, V>* _right;
	 AVLTreeNode<K, V>* _parent;

	 int _bf; // balance factor

	 AVLTreeNode(const pair<K, V>& kv)
		 :_kv(kv)
		 , _left(nullptr)
		 , _right(nullptr)
		 , _parent(nullptr)
		 , _bf(0)
	 {}
 };

 template<class K,class V>
 class AVLTree
 {
	 typedef AVLTreeNode<K,V> Node;
 public:
	 AVLTree()
		 : _root(nullptr)
	 {}

	 bool Insert(const pair<K, V>& kv)
	 {

		 if (_root == nullptr)
		 {
			 _root = new Node(kv);

			 return true;
		 }

		 Node* cur = _root;
		 Node* parent = _root;

		 while (cur)
		 {
			 if (kv.first < cur->_kv.first)
			 {
				 parent = cur;
				 cur = cur->_left;
			 }
			 else if (kv.first > cur->_kv.first)
			 {
				 parent = cur;
				 cur = cur->_right;
			 }
			 else
				 return true;
		 }

		 cur = new Node(kv);

		 if (parent->_kv.first > kv.first)
		 {
			 parent->_left = cur;
			 cur->_parent = parent;
		 }
		 else
		 {
			 parent->_right = cur;
			 cur->_parent = parent;
		 }

		 //平衡因子更新
		 while (parent)
		 {

			 if (parent->_left == cur)
				 parent->_bf--;
			 else
				 parent->_bf++;

			 if (parent->_bf == 0)
				 break;
			 else if (parent->_bf == 1 || parent->_bf == -1)
			 {
				 cur = parent;
				 parent = parent->_parent;
			 }
			 else if (parent->_bf == 2 || parent->_bf == -2)
			 {
				 //旋转 
				 if (parent->_bf == -2 && cur->_bf == -1)
				 {
					 //右单旋
					 RotateR(parent);
				 }
				 else if (parent->_bf == 2 && cur->_bf == 1)
				 {
					 //左单旋
					 RotateL(parent);
				 }
				 else if (parent->_bf == -2 && cur->_bf == 1)
				 {
					 //左右双旋
					 RotateLR(parent);
				 }
				 else if (parent->_bf == 2 && cur->_bf == -1)
				 {
					 //右左双旋
					 RotateRL(parent);
				 }
				 else
				 {
					assert(false);
				 }

				 break;
			 }
			 else
				 assert(false);
			 
		 }
		 return true;
	 }

	 void RotateR(Node* parent)
	 {
		 Node* subL = parent->_left;
		 Node* subLR = subL->_right;

		 parent->_left = subLR;
		 if (subLR)
			 subLR->_parent = parent;

		 Node* pParent = parent->_parent;

		 subL->_right = parent;
		 parent->_parent = subL;

		 if (parent == _root)
		 {
			 _root = subL;
			 subL->_parent = nullptr;
		 }
		 else
		 {
			 if (pParent->_left == parent)
			 {
				 pParent->_left = subL;
			 }
			 else
			 {
				 pParent->_right = subL;
			 }

			 subL->_parent = pParent;
		 }

		 subL->_bf = 0;
		 parent->_bf = 0;
	 }

	 void RotateL(Node* parent)
	 {
		 Node* subR = parent->_right;
		 Node* subRL = parent->_right->_left;

		 parent->_right = subRL;
		 if (subRL)
			 subRL->_parent = parent;

		 subR->_left = parent;

		 Node* pParent = parent->_parent;

		 parent->_parent = subR;
		 subR->_parent = pParent;

		 if (pParent == nullptr)
		 {
			_root = subR;
			subR->_parent = nullptr;;

		 }
		 else
		 {
			 if (pParent->_left == parent)
			 {
				 pParent->_left = subR;
			 }
			 else
			 {
				 pParent->_right = subR;

			 }
			 subR->_parent = pParent;

		 }
		 parent->_bf = 0;
		 subR->_bf = 0;

	 }


	 void RotateLR(Node* parent)
	 {

		 Node* subL = parent->_left;
		 Node* subLR = subL->_right;
		 int bf = subLR->_bf;

		 RotateL(parent->_left);
		 RotateR(parent);

		 if (bf == 0)
		 {
			 subL->_bf = 0;
			 subLR->_bf = 0;
			 parent->_bf = 0;
		 }
		 else if (bf == -1)
		 {
			 subL->_bf = 0;
			 subLR->_bf = 0;
			 parent->_bf = 1;
		 }
		 else if (bf == -1)
		 {
			 subL->_bf = -1;
			 subLR->_bf = 0;
			 parent->_bf = 0;
		 }
		 else
			 assert(false);

	 }

	 void RotateRL(Node* parent)
	 {
		 Node* subR = parent->_right;
		 Node* subRL = subR->_left;
		 int bf = subRL->_bf;

		 RotateR(parent->_right);
		 RotateL(parent);

		 if (bf == 0)
		 {
			 subR->_bf = 0;
			 subRL->_bf = 0;
			 parent->_bf = 0;
		 }
		 else if (bf == 1)
		 {
			 subR->_bf = 0;
			 subRL->_bf = 0;
			 parent->_bf = -1;
		 }
		 else if (bf == -1)
		 {
			 subR->_bf = 1;
			 subRL->_bf = 0;
			 parent->_bf = 0;
		 }
		 else
		 {
			 assert(false);
		 }
	 }

	 Node* Find(const K& key)
	 {
		 Node* cur = _root;
		 while (cur)
		 {
			 if (cur->_kv.first < key)
			 {
				 cur = cur->_right;
			 }
			 else if (cur->_kv.first > key)
			 {
				 cur = cur->_left;
			 }
			 else
			 {
				 return cur;
			 }
		 }
		 return nullptr;
	 }

	 int Height()
	 {
		 return _Height(_root);
	 }

	 bool IsBalanceTree()
	 {
		 return  _IsBalanceTree(_root);
	 }
	 void InOrder()
	 {
		 _InOrder(_root);
	 }

private:

	 int _Height(Node* root)
	 {
		 if (root == nullptr)
			 return 0;
		 int leftHeight = _Height(root->_left);
		 int rightHeight = _Height(root->_right);
		 return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	 }

	 bool _IsBalanceTree(Node* root)
	 {
		 // 空树也是AVL树
		 if (nullptr == root)
			 return true;
		 // 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
		 int leftHeight = _Height(root->_left);
		 int rightHeight = _Height(root->_right);
		 int diff = rightHeight - leftHeight;
		 // 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者
// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
		 if (abs(diff) >= 2)
		 {
			 cout << root->_kv.first << "高度差异常" << endl;
			 return false;
		 }
		 if (root->_bf != diff)
		 {
			 cout << root->_kv.first << "平衡因子差异" << endl;
			 return false;
		 }
		 // pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
		 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	 }

	 void _InOrder(Node* root)
	 {
		 if (root == nullptr)
			 return;
		 _InOrder(root->_left);
		 cout << root->_kv.first << ":" << root->_kv.second << endl;
		 _InOrder(root->_right);
	 }
 private:
	 Node* _root;
 };